An electronic computer aided design (“E-CAD”) tool is used to create and analyze a circuit design, including a very large scale integration (“VLSI”) circuit design. The circuit design includes a netlist that identifies electronic design elements (e.g., capacitors, transistors, resistors, etc.) and their interconnectivity (e.g., nets) within the circuit design.
A signal net is a single electrical path in a circuit design that has the same electrical characteristics at all of its points. Any collection of wires that carries the same signal between design elements is a signal net. If the design elements allow the signal to pass through unaltered (as in the case of a terminal), then the signal net continues on subsequently connected wires. If, however, the design element modifies the signal (as in the case of a transistor or logic gate), then the signal net terminates at that design element and a signal new net begins on the other side.
A significant characteristic of VLSI and other types of circuit design is a reliance on hierarchical description. A primary reason for using hierarchical description is to hide the vast amount of detail in a circuit design. By reducing the distracting detail to a single object that is lower in the hierarchy, one can greatly simplify many E-CAD operations. For example, simulation, verification, design-rule checking, and layout constraints can all benefit from hierarchical representation, which makes them more computationally tractable. Since many circuit designs are too complicated to be easily considered in their totality, a complete design is often viewed as a collection of design element aggregates that are further divided into sub-aggregates in a recursive and hierarchical manner. In VLSI circuit design, these aggregates are commonly referred to as design blocks (or cells). The use of a design block at a given level of hierarchy is called an ‘instance’. Each design block has one or more ‘ports’, each of which provides a connection point between a signal net within the design block and a signal net external to the design block. A net within one design block may thereby connect with a net in another design block, the net ‘pieces’ forming a single net known as a ‘highest level signal name’ (“HLSN”). The HLSN is identified by the name of the net ‘piece’ located at the highest hierarchical level in the circuit design.
When tracing signal paths through a hierarchical circuit design, it is often desirable to know the HLSN of a given net, other than the one being traced. This situation can occur, for example, when a terminal of a device is reached at some level of the hierarchical design, and the HLSN of one or more other terminals for that device needs to be determined. Presently known tracing strategies typically use recursive methods that employ complex algorithms that redundantly analyze a circuit design, and which are conceptually non-intuitive to developers of E-CAD tools.
Tracing a hierarchical circuit design can be a tedious process to implement. The following pseudo-code illustrates one manner in which the trace has typically heretofore been performed. Initially, an initial net is selected. Then, a routine (such as ‘RECURSE’, below) is employed to recursively traverse the hierarchical design for each port and port instance on the net.
RECURSE:DoSomeStuff (net)foreach portinst on net {get instance owner of portinstget describer of instanceget port describer of portinstpush instance onto instance_histget net on portRECURSE(net, instance_hist)}foreach port on net {get instance from instance_histget portinst instantiation of portpop instance off instance_histget net on portinstRECURSE(net, instance_hist)}END RECURSE
The above recursive routine is executionally redundant, and therefore not particularly efficient, and can thus require a great deal of processor time to traverse a typical VLSI circuit design, particularly when an analysis tool needs to iterate over nets in the design to determine properties or quantities unrelated to the circuit hierarchy. The problem of traversals can become even more complicated when the capability of skipping ‘around’ elements in the design is desired. For instance, if a field-effect transistor (“FET”) is encountered in tracing through a circuit design, it may be necessary to skip to the opposite side of the FET (e.g., source to drain, or drain to source) and continue tracing.